package com.ztom.v2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ZhangTao
 */
public class Code62NQueens {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();

        int[] record = new int[n];
        process(0, n, record, res);
        return res;
    }

    public void process(int row, int n, int[] record, List<List<String>> res) {
        if (row == n) {
            List<String> list = new ArrayList<>();
            for (int r = 0; r < n; r++) {
                char[] chars = new char[n];
                for (int c = 0; c < n; c++) {
                    if (record[r] == c) {
                        chars[c] = 'Q';
                    } else {
                        chars[c] = '.';
                    }
                }
                list.add(String.valueOf(chars));
            }
            res.add(list);
            return;
        }

        // 枚举当前行放在某一列是否可行
        for (int c = 0; c < n; c++) {
            if (isValid(row, c, record)) {
                record[row] = c;
                process(row + 1, n, record, res);
            }
        }
    }

    public boolean isValid(int row, int col, int[] record) {
        // 检查是否与历史行冲突
        for (int k = 0; k < row; k++) {
            if (record[k] == col || Math.abs(row - k) == Math.abs(col - record[k])) {
                return false;
            }
        }
        return true;
    }
}
